package com.Algorithm.HUAWEI.four20220505;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.nio.Buffer;
import java.util.Arrays;
import java.util.Comparator;

/**
 * Created with IntelliJ IDEA.
 *
 * @Author: zjz
 * @Date: 2022/05/20/17:31
 * @Description:
 * @Target:
 */
public class 成绩排序 {
    /*
    *
    * 描述
        给定一些同学的信息（名字，成绩）序列，请你将他们的信息按照成绩从高到低或从低到高的排列,相同成绩
        都按先录入排列在前的规则处理。

        例示：
        jack      70
        peter     96
        Tom       70
        smith     67

        从高到低  成绩
        peter     96
        jack      70
        Tom       70
        smith     67

        从低到高

        smith     67
        jack      70
        Tom       70
        peter     96

        注：0代表从高到低，1代表从低到高

        数据范围：人数：1≤n≤200
        进阶：时间复杂度：O(nlogn) ，空间复杂度：O(n)
        输入描述：
        第一行输入要排序的人的个数n，第二行输入一个整数表示排序的方式，之后n行分别输入他们的名字和成绩，以一个空格隔开

        输出描述：
        按照指定方式输出名字和成绩，名字和成绩之间以一个空格隔开

        示例1
        输入：
        3
        0
        fang 90
        yang 50
        ning 70

        输出：
        fang 90
        ning 70
        yang 50
        复制
        示例2
        输入：
        3
        1
        fang 90
        yang 50
        ning 70

        输出：
        yang 50
        ning 70
        fang 90

    *
    * */

    static int AscOrDescFlag;  // 升序，降序标志
    public static void main(String[] args) throws IOException {
//        int[] ints = new int[]{2,65,5,1,6,9,7,5};


        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.valueOf(in.readLine());
        AscOrDescFlag= Integer.valueOf(in.readLine());
        Student[] students = new Student[N];
        for (int i = 0; i < N; i++) {
            students[i] = new Student();
            String[] s = in.readLine().split(" ");
            students[i].setName(s[0]);
            students[i].setGrade(Integer.valueOf(s[1]));
        }
        /*
        students[0] = new Student("HH0",95);
        students[1] = new Student("HH1",96);
        students[2] = new Student("HH2",94);
*/



/*        mergeSort(ints);
        for (int anInt : ints) {
            System.out.print(anInt+",");
        }*/
        mergeStudentSort(students);

        for (Student student : students) {
            System.out.println(student.getName()+" "+student.getGrade());
        }



    }







    // 排序算法有了，学生类也有了,如何给对象属性排序
    // 发现只能是给学生弄值了、
    // 学生数组，每个里面是学生


    static class Student{
        private String name;
        private int grade;

        public Student() {
        }

        public Student(String name, int grade) {
            this.name = name;
            this.grade = grade;
        }

        public String getName() {
            return name;
        }

        public void setName(String name) {
            this.name = name;
        }

        public int getGrade() {
            return grade;
        }

        public void setGrade(int grade) {
            this.grade = grade;
        }

        @Override
        public String toString() {
            return "Student{" +
                    "name='" + name + '\'' +
                    ", grade=" + grade +
                    '}';
        }
    }

    static void mergeSort(int[] ints){
        mergeProcess(ints,0,ints.length-1);
    }

    static void mergeProcess(int[] ints,int leftIndex,int rightIndex){

        if (leftIndex==rightIndex){
            return;
        }

        // 如果直接R-L/2的话。。。想想数轴，L在8，R在10，m=1...
        int mid = leftIndex + ((rightIndex-leftIndex)>>1);

        mergeProcess(ints,leftIndex,mid);
        mergeProcess(ints,mid+1,rightIndex);
        mergeStep(ints,leftIndex,mid,rightIndex);
    }


    // merge 排序
    static void mergeStep(int[] ints,int leftIndex,int midIndex,int rightIndex){
        // 左树，右树
        int[] tempArray = new int[rightIndex-leftIndex+1];
        int LP = leftIndex;
        int MP = midIndex+1;
        int tempIndex = 0;
        while (LP<=midIndex && MP<=rightIndex){
            tempArray[tempIndex++] = ints[LP] <= ints[MP]?ints[LP++]:ints[MP++];
        }



        while (LP<=midIndex){
            tempArray[tempIndex++] = ints[LP++];
        }

        while (MP<=rightIndex){
            tempArray[tempIndex++] = ints[MP++];
        }


        // 临时数据导入原数组
        for (int i = 0; i < tempArray.length; i++) {
            ints[leftIndex+i] = tempArray[i];
        }

    }



    static void mergeStudentSort(Student[] students){
        mergeProcessAscOrDesc(students,0,students.length-1);
    }

    static void mergeProcessAscOrDesc(Student[] students,int leftIndex,int rightIndex){

        if (leftIndex==rightIndex){
            return;
        }

        // 如果直接R-L/2的话。。。想想数轴，L在8，R在10，m=1...
        int mid = leftIndex + ((rightIndex-leftIndex)>>1);

        mergeProcessAscOrDesc(students,leftIndex,mid);
        mergeProcessAscOrDesc(students,mid+1,rightIndex);
        if (AscOrDescFlag==1){
            mergeStepAsc(students,leftIndex,mid,rightIndex);
        }else {
            mergeStepDesc(students,leftIndex,mid,rightIndex);
        }

    }

    // merge 排序，升序
    static void mergeStepAsc(Student[] students,int leftIndex,int midIndex,int rightIndex){
        // 左树，右树
        Student[] tempArray = new Student[rightIndex-leftIndex+1];
        int LP = leftIndex;
        int MP = midIndex+1;
        int tempIndex = 0;
        while (LP<=midIndex && MP<=rightIndex){
            tempArray[tempIndex++] = students[LP].getGrade() <= students[MP].getGrade()?students[LP++]:students[MP++];
        }



        while (LP<=midIndex){
            tempArray[tempIndex++] = students[LP++];
        }

        while (MP<=rightIndex){
            tempArray[tempIndex++] = students[MP++];
        }


        // 临时数据导入原数组
        for (int i = 0; i < tempArray.length; i++) {
            students[leftIndex+i] = tempArray[i];
        }

    }

    // merge 排序，降序
    static void mergeStepDesc(Student[] students,int leftIndex,int midIndex,int rightIndex){
        // 左树，右树
        Student[] tempArray = new Student[rightIndex-leftIndex+1];
        int LP = leftIndex;
        int MP = midIndex+1;
        int tempIndex = 0;
        while (LP<=midIndex && MP<=rightIndex){
            tempArray[tempIndex++] = students[LP].getGrade() >= students[MP].getGrade()?students[LP++]:students[MP++];
        }



        while (LP<=midIndex){
            tempArray[tempIndex++] = students[LP++];
        }

        while (MP<=rightIndex){
            tempArray[tempIndex++] = students[MP++];
        }


        // 临时数据导入原数组
        for (int i = 0; i < tempArray.length; i++) {
            students[leftIndex+i] = tempArray[i];
        }

    }


}
